1. Field of the Invention
The present invention relates to signal processing techniques, and particularly to a method of performing structure-based Bayesian sparse signal reconstruction.
2. Description of the Related Art
Compressive Sensing/Compressed Sampling (CS) is a fairly new field of research that is finding many applications in statistics and signal processing. As its name suggests, CS attempts to acquire a signal (inherently sparse in some subspace) at a compressed rate by randomly projecting it onto a subspace that is much smaller than the dimension of the signal itself. Provided that the sensing matrix satisfies a few conditions, the sparsity pattern of such a signal can be recovered non-combinatorially with high probability. This is in direct contrast to the traditional approach of sampling signals according to the Nyquist theorem and then discarding the insignificant samples.
Generally, most naturally occurring signals are sparse in some basis/domain, and therefore CS can be utilized for their reconstruction. CS has been used successfully in, for example, peak-to-average power ratio reduction in orthogonal frequency division multiplexing (OFDM), image processing, impulse noise estimation and cancellation in power-line communication and digital subscriber lines (DSL), magnetic resonance imaging (MRI), channel estimation in communications systems, ultra-wideband (UWB) channel estimation, direction-of-arrival (DOA) estimation, and radar design.
The CS problem can be described as follows. Let x ∈ CN be a P-sparse signal (i.e., a signal that consists of P non-zero coefficients in an N-dimensional space with P<<N) in some domain, and let y ∈ CM be the observation vector with M<<N given by:y=Ψx+n,  (1)where Ψ is an M×N measurement/sensing matrix that is assumed to be incoherent with the domain in which x is sparse, and n is complex additive white Gaussian noise, CN(0, σn2Im). As M<<N, this is an ill-posed problem as there is an infinite number of solutions for x satisfying equation (1). If it is known a priori that x is sparse, the theoretical way to reconstruct the signal is to solve an l0-norm minimization problem using only M=2P measurements when the signal and measurements are free of noise:
                    x        =                                            min              x                        ⁢                                                                              x                                                  0                            ⁢                                                          ⁢              subject              ⁢                                                          ⁢              to              ⁢                                                          ⁢              y                                =                      Ψ            ⁢                                                  ⁢                          x              .                                                          (        2        )            
Unfortunately, solving the l0-norm minimization problem is NP-hard, and is therefore not practical. Thus, different sub-optimal approaches, categorized as compressive sensing, have been developed to solve this problem. It has been shown that x can be reconstructed with high probability in polynomial time by using convex relaxation approaches, at the cost of an increase in the required number of measurements. This is performed by solving a relaxed l1-norm minimization problem using linear programming instead of l0-norm minimization:
                              x          =                                                    min                x                            ⁢                                                                                        x                                                        1                                ⁢                                                                  ⁢                subject                ⁢                                                                  ⁢                to                ⁢                                                                  ⁢                                                                                                y                      -                                              Ψ                        ⁢                                                                                                  ⁢                        x                                                                                                  2                                                      ≤            ɛ                          ,                            (        3        )            where
  ɛ  =                              σ          n          2                ⁡                  (                      M            +                                          2                ⁢                M                                              )                      .  For ll-norm minimization to reconstruct the sparse signal accurately, the sensing matrix Ψ should be sufficiently incoherent. In other words, the coherence, defined as μ(Ψ)maxi≠j|ΨiΨj|, should be as small as possible (with μ(Ψ)=1 depicting the worst case). It has been shown that these convex relaxation approaches have a Bayesian rendition and may be viewed as maximizing the maximum a posteriori estimate of x, given that x has a Laplacian distribution. Although convex relaxation approaches are able to recover sparse signals by solving under-determined systems of equations, they also suffer from a number of drawbacks, as discussed below.
Convex relaxation relies on linear programming to solve the convex l1-norm minimization problem, which is computationally relatively complex (its complexity is of the order 0(M2N3/2) when interior point methods are used. This approach can, therefore, not be used in problems with very large dimensions. To overcome this drawback, many “greedy” algorithms have been proposed that recover the sparse signal iteratively. These include Orthogonal Matching Pursuit (OMP), Regularized Orthogonal Matching Pursuit (ROMP), Stagewise Orthogonal Matching Pursuit (StOMP), and Compressive Sampling Matching Pursuit (CoSamp). These greedy approaches are relatively faster than their convex relaxation counterparts (approximately 0(MNR), where R is the number of iterations).
Convex relaxation methods cannot make use of the structure exhibited by the sensing matrix (e.g., a structure that comes from a Toeplitz sensing matrix or that of a partial discrete Fourier transform (DFT) matrix). In fact, if anything, this structure is harmful to these methods, as the best results are obtained when the sensing matrix is close to random. This is in contrast to current digital signal processing architectures that only deal with uniform sampling. Obviously, more feasible and standard sub-sampling approaches would be desirable.
Convex relaxation methods are further not able to take account of any a priori statistical information (apart from sparsity information) about the signal support and additive noise. Any a priori statistical information can be used on the result obtained from the convex relaxation method to refine both the signal support obtained and the resulting estimate through a hypothesis testing approach. However, this is only useful if these approaches are indeed able to recover the signal support. In other words, performance is bottle-necked by the support-recovering capability of these approaches. It should be noted that the use of a priori statistical information for sparse signal recovery has been studied in a Bayesian context, and in algorithms based on belief propagation, although the former uses a priori statistical information (assuming x to be mixed Bernoulli-Gaussian), and only the latter uses this information in a recursive manner to obtain a fast sparse signal recovery algorithm. However, it is not clear how these approaches can be extended to the non-Gaussian case.
It is difficult to quantify the performance of convex relaxation estimates analytically in terms of the mean squared error (MSE) or bias, or to relate these estimates to those obtained through more conventional approaches, e.g., maximum a posteriori probability (MAP), minimum mean-square error (MMSE), or maximum likelihood (ML). It should be noted that convex relaxation approaches have their merits, in that they are agnostic to the signal distribution and thus can be quite useful when worst-case analysis is desired, as opposed to average-case analysis.
In general, convex relaxation approaches do not exhibit the customary tradeoff between increased computational complexity and improved recovery, as is the case for, as an example, iterative decoding, or joint channel and data detection. Rather, they solve some l1 problem using (second-order cone programming) with a set complexity. Some research has been directed towards attempting to derive sharp thresholds for support recovery. In other words, the only degree of freedom available for the designer to improve performance is to increase the number of measurements. Several iterative implementations of convex relaxation approaches provide some sort of flexibility by trading performance for complexity.
It should be noted that in the above, and in what follows, scalars are identified with lower-case letters (e.g., x), vectors are identified with lower-case bold-faced letters (e.g., x), matrices are represented by upper-case, bold-faced letters (e.g., X), and sets are identified with script notation (e.g. S). The format of xi is used to denote the ith column of matrix X, x(j) denotes the jth entry of vector x, and Si denotes a subset of a set S. XS is used to denote the sub-matrix formed by the columns {xi: i ∈S}, indexed by the set S. Finally, x, x*, xT, and xH are used to denote the estimate, conjugate, transpose, and conjugate transpose, respectively, of a vector x.
The signal model is of particular interest, particularly in regard to equation (1). Here, the vector x is modelled as x=xB ⊙ xG, where ⊙ denotes the Hadamard (element-by-element) multiplication. The entries of xB are independent and identically distributed Bernoulli random variables and the entries of xG are drawn identically and independently from some zero mean distribution. In other words, it is assumed that xB(i) are Bernoulli with success probability p, and similarly, that the xG(i) are independent and identically distributed (i.i.d.) variables with marginal probability distribution function f(x). The noise n is assumed to be complex circularly symmetric Gaussian, i.e., n˜CN(0, σn2IM). When the support set S of x is known, equation (1) can be equivalently expressed as:y=ΨSxS+n.  (4)
The ultimate objective is to obtain the optimum estimate of x given the observation y. Either an MMSE or a MAP approach may be used to achieve this goal. The MMSE estimate of x given the observation y can be expressed as:
                                          x            ^                    MMSE                =                                          ⁡                          [                              x                |                y                            ]                                =                                    Σ              S                        ⁢                          p              ⁡                              (                                  S                  |                  y                                )                                      ⁢                                        ⁡                              [                                                      x                    |                    y                                    ,                  S                                ]                                                                        (        5        )            where the sum is over all the possible support sets S of x. The likelihood and expectation involved in equation (5) are evaluated below.
With regard to the evaluation of [x|y, S], we note that the relationship between y and x is linear. Thus, in the case where x conditioned on its support is Gaussian, [x|y, S] is simply the linear MMSE estimate of x given y (and S), i.e.:
                                                      ⁡                          [                                                x                  S                                |                y                            ]                                ⁢                      =            Δ                    ⁢                                                  ⁡                              [                                                      x                    |                    y                                    ,                  S                                ]                                      =                                          σ                x                2                            ⁢                              Ψ                S                H                            ⁢                              Σ                S                                  -                  1                                            ⁢              y                                      ,                            (        6        )            where
                              Σ          S                =                                            1                              σ                n                2                                      ⁢                                        ⁡                              [                                                      yy                    H                                    |                  S                                ]                                              =                                    I              M                        +                                                            σ                  x                  2                                                  σ                  n                  2                                            ⁢                              Ψ                S                            ⁢                                                Ψ                  S                  H                                .                                                                        (        7        )            
When x|S is non-Gaussian or when its statistics are unknown, the expectation [x|y, S] is difficult or even impossible to calculate. Thus, it may be replaced by the best linear unbiased estimate (BLUE), i.e.:
                                        ⁡                      [                                          x                S                            |              y                        ]                          =                                            (                                                Ψ                  S                  H                                ⁢                                  Ψ                  S                                            )                                      -              1                                ⁢                      Ψ            S            H                    ⁢                      y            .                                              (        8        )            
With regard to the evaluation of p(S|y), using Bayes' rule, p(S|y) may be rewritten as:
                              p          ⁡                      (                          S              |              y                        )                          =                                                            p                ⁡                                  (                                      y                    |                    S                                    )                                            ⁢                              p                ⁡                                  (                  S                  )                                                                                    Σ                S                            ⁢                              p                ⁡                                  (                                      y                    |                    S                                    )                                            ⁢                              p                ⁡                                  (                  S                  )                                                              .                                    (        9        )            
As the denominator Σs p(y|S)p(S) is common to all posterior likelihoods, p(S|y), it is a normalizing constant that can be ignored. To evaluate p(S), it should be noted that the elements of x are active according to a Bernoulli process with success probability p. Thus, p(S) is given by:p(S)=p|S|(1−p)N−|S|.  (10)
What remains is the evaluation p(y|S), distinguishing between the cases of whether or not x|S is Gaussian. When x|S is Gaussian, y is also Gaussian, with zero mean and covariance ΣS. The likelihood function may be written as:
                              p          ⁡                      (                          y              |              S                        )                          =                              exp            ⁡                          (                                                -                                      1                                          σ                      n                      2                                                                      ⁢                                                                          y                                                                            Σ                    S                                          -                      1                                                        2                                            )                                            det            ⁡                          (                              Σ                S                            )                                                          (        11        )            up to an irrelevant constant multiplicative factor, (1/πM), where ∥b∥A2bHAb.
When x|S is non-Gaussian or unknown, then alternatively, we may treat x as a random vector of unknown (non-Gaussian) distribution, with support S. Therefore, given the support S, all that can be said about y is that it is formed by a vector in the subspace spanned by the columns of ΨS, plus a white Gaussian noise vector, n. It is difficult to quantify the distribution of y, even if we know the distribution of (the non-Gaussian) x. One way around this is to annihilate the non-Gaussian component and retain the Gaussian one. This is performed by projecting y onto the orthogonal complement of the span of the columns of ΨS, i.e., multiplying y by PS⊥=I−ΨS(ΨSHΨS)−1ΨSH. This leaves PS⊥y=PS⊥n, which is zero mean and with covariance PS⊥σn2PS⊥H=σn2PS⊥. Thus, the conditional density of y given S is approximately given by
                              p          ⁡                      (                          y              |              S                        )                          ≃                              exp            ⁡                          (                                                -                                      1                                          σ                      n                      2                                                                      ⁢                                                                                                                        P                        S                        ⊥                                            ⁢                      y                                                                            2                                            )                                .                                    (        12        )            
To obtain the MAP estimate of x, the MAP estimate of S must first be determined, which is given by
                                          S            ^                    MAP                =                  arg          ⁢                                          ⁢                                    max              S                        ⁢                                          p                ⁡                                  (                                      y                    |                    S                                    )                                            ⁢                                                p                  ⁡                                      (                    S                    )                                                  .                                                                        (        13        )            
The prior likelihood p(y|S) is given by equation (11) when x|S is Gaussian and by equation (12) when x|S is non-Gaussian or unknown, whereas p(S) is evaluated using equation (10). The maximization is performed over all possible 2N support sets. The corresponding MAP estimate of x is given by{circumflex over (x)}MAP=[x|y, SMAP].  (14)
One can easily see that the MAP estimate is a special case of the MMSE estimate in which the sum of equation (5) is reduced to one term. As a result, we are ultimately interested in MMSE estimation.
Having evaluated the posterior probability and expectation, it remains to evaluate this over 2N possible supports (see equation (5) and equation (13)), which is a computationally daunting task. This is compounded by the fact that the calculations required for each support set in S are relatively expensive, requiring some form of matrix multiplication/inversion as can be seen from equations (6)-(12). One way around this exhaustive approach is somehow to guess at a superset Sr consisting of the most probable support, and then limit the sum in equation (5) to the superset Sr and its subsets, reducing the evaluation space to 2|Sr| points. There are two techniques that aid in guessing at such a set Sr: convex relaxation and the Fast Bayesian Maching Pursuit (FBMP).
In convex relaxation, starting from equation (1), standard convex relaxation tools may be used to find the most probable support set Sr of the sparse vector x. This is performed by solving equation (3) and retaining some largest P non-zero values, where P is selected such that P(∥S∥0>P) is very small. As ∥S∥0 is a binomial distribution ˜B(N, p), it can be approximated by a Gaussian distribution ˜N(Np, Np(1−p)), when Np>5 (the DeMoivre-Laplace approximation). In this case,
      P    ⁡          (                                                S                                0                >        P            )        =            1      2        ⁢                  erfc        ⁡                  (                                    P              -                              N                ⁡                                  (                                      1                    -                    p                                    )                                                                                    (                                  2                  ⁢                                                                          ⁢                                      Np                    ⁡                                          (                                              1                        -                        p                                            )                                                                      )                                              )                    .      
FBMP is a fast Bayesian recursive algorithm that determines the dominant support and the corresponding MMSE estimate of the sparse vector. It should be noted that FBMP applies to the Bernoulli Gaussian case only. FBMP uses a greedy tree search over all combinations in pursuit of the dominant supports. The algorithm starts with zero active element support set. At each step, an active element is added that maximizes the Gaussian log-likelihood function similar to equation (11). This procedure is repeated until P active elements in a branch are reached. The procedure creates D such branches, which represent a tradeoff between performance and complexity. Though other greedy algorithms can also be used, FBMP is focused on here as it utilizes a priori statistical information along with sparsity information.
The above applies irrespective of the type of the sensing matrix Ψ. However, in many applications in signal processing and communications, the sensing matrix is highly structured. It would be desirable to take advantage of this in order to evaluate the MMSE (MAP) estimate at a much lower complexity than is currently available.
In most CS applications, the sensing matrix Ψ is assumed to be drawn from a random constellation, and in many signal processing and communications applications, this matrix is highly structured. Thus, Ψ could be a partial discrete Fourier transform (DFT) matrix or a Toeplitz matrix (encountered in many convolution applications). Table 1 below lists various possibilities of structured Ψ:
TABLE 1Applications of Structured Sensing MatricesMatrix ΨApplicationPartial DFTOFDM applications including peak-to-average powerratio reduction, narrow-band interference cancelationand impulsive noise estimation and mitigation in DSLToeplitzChannel estimation, UWB and DOA estimationHankelWide-band spectrum sensingDCTImage compressionStructured BinaryMulti-user detection and contention resolution andfeedback reduction
Since Ψ is a “fat” matrix (M<<N), its columns are not orthogonal (in fact, they are not even linearly independent). However, in the aforementioned applications, one can usually find an orthogonal subset of the columns of Ψ that span the column space of Ψ. These columns may be collected into a square matrix ΨM. The remaining (N−M) columns of Ψ group around these orthogonal columns to form semi-orthogonal clusters. In general, the columns of Ψ can be rearranged such that the farther two columns are from each other, the lower their correlation is. Below, it will be seen how semi-orthogonality helps to evaluate the MMSE estimate in a “divide-and-conquer” manner. Prior to this, it will first be demonstrated that the DFT and Toeplitz/Hankel sensing matrices exhibit semi-orthogonality.
For a partial DFT matrix, Ψ=SFN, where FN denotes the N×N unitary DFT matrix, [FN]a,b=(1/√{square root over (N)})e−j2πa,b/N with a, b ∈{0,1, . . . , N−1} and S is an M×N selection matrix consisting of zeros with exactly one entry equal to 1 per row. To enforce the desired semi-orthogonal structure, the matrix S usually takes the form S=[0M×Z IM×M OM×(N−Z−M)], for some integer Z. In other words, the sensing matrix consists of a continuous band of sensing frequencies. This is not unusual, since in many OFDM problems, the band of interest (or the one free of transmission) is continuous. In this case, the correlation between two columns can be shown to be
                                          ψ            k            H                    ⁢                      ψ                          k              ′                                      =                  {                                                                      1                  ,                                                                              (                                      k                    =                                          k                      ′                                                        )                                                                                                                                                                                            sin                        ⁡                                                  (                                                                                    π                              ⁡                                                              (                                                                  k                                  -                                                                      k                                    ′                                                                                                  )                                                                                      ⁢                                                          M                              /                              N                                                                                )                                                                                            M                        ⁢                                                                                                  ⁢                                                  sin                          ⁡                                                      (                                                                                          π                                ⁡                                                                  (                                                                      k                                    -                                                                          k                                      ′                                                                                                        )                                                                                            /                              N                                                        )                                                                                                                                                    ,                                                                              (                                      k                    ≠                                          k                      ′                                                        )                                                                                        (        15        )            which is a function of the difference, (k−k′) mod N. It thus suffices to consider the correlation of one column with the remaining ones. It should be noted that the matrix Ψ exhibits other structural properties (e.g., the fact that it is a Vandermonde matrix), which helps to reduce the complexity of MMSE estimation.
For the Toeplitz case, which can be easily extended to the Hankel case, a sub-sampled convolutional linear system can be written in the following matrix form, y=Ψx+n, where y is a vector of length M, x is a vector of length N and Ψ is the M×N block Toeplitz/diagonal matrix:
      Ψ    =          [                                    Θ                                0                                …                                0                                                0                                Θ                                …                                0                                                ⋮                                ⋱                                ⋱                                ⋮                                                0                                0                                …                                Θ                              ]        ,where the size of Θ depends on the sub-sampling ratio. Here, ΨkHΨk′=0 for |k−k′|>L, and thus the columns of Ψ can easily be grouped into truly orthogonal clusters. It should be noted that the individual columns of Θ are related to each other by a shift property.
In order to use orthogonality for MMSE estimation, we let S be a possible support of x. The columns of ΨS in equation (4) can be grouped into a maximum of C semi-orthogonal clusters, i.e., ΨS=[ΨS1 ΨS2 . . . ΨSC], where Si is the support set corresponding to the ith cluster (with i=1,2, . . . C). Based on this fact, equation (4) can be written as:
                    y        =                  [                                                                                                                Ψ                                              S                        1                                                                                                                        Ψ                                              S                        2                                                                                                  …                                                                                                      Ψ                                                  S                          C                                                                    ]                                                                                  ⁡                              [                                                                                                    x                        1                                                                                                                                                x                        2                                                                                                                        ⋮                                                                                                                          x                        C                                                                                            ]                                      +                          n              .                                                          (        16        )            
Columns indexed by these sets should be semi-orthogonal, i.e., ΨSiHΨSj≃0; otherwise, Si and Sj are merged into a bigger superset. Thus, the MMSE estimate of x simplifies to:
                              x          MMSE                =                              ∑                          Z              ⋐                              ⋃                                  S                  i                                                              ⁢                                    p              ⁡                              (                                  Z                  |                  y                                )                                      ⁢                                          𝔼                ⁡                                  [                                                            x                      |                      y                                        ,                    Z                                    ]                                            .                                                          (        17        )            
In order to see that xMMSE can be evaluated in a “divide-and-conquer” manner by treating each cluster independently, it must first be shown how orthogonality manifests itself in the calculation of the expectation and likelihood. Up to a constant factor, the likelihood can be written as p(Z|y)=p(y|Z)p(Z). Thus:
                                                                        p                ⁡                                  (                  Z                  )                                            =                            ⁢                              p                ⁡                                  (                                      ⋃                                          Z                      i                                                        )                                                                                                        =                            ⁢                                                                    p                                                                                        ⋃                                                  Z                          i                                                                                                                            ⁡                                      (                                          1                      -                      p                                        )                                                                    N                  -                                                                                ⋃                                              Z                        i                                                                                                                                                                                        =                            ⁢                                                                    p                                                                                                                    Z                          1                                                                                            +                                                                                                Z                          2                                                                                            +                      …                      +                                                                                                Z                          C                                                                                                                              ⁡                                      (                                          1                      -                      p                                        )                                                                    N                  -                                      (                                                                                                                    Z                          1                                                                                            +                                                                                                Z                          2                                                                                            +                      …                      +                                                                                                Z                          C                                                                                                              )                                                                                                                          =                            ⁢                                                p                  ⁡                                      (                                          Z                      1                                        )                                                  ⁢                                  p                  ⁡                                      (                                          Z                      2                                        )                                                  ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                                  p                  ⁡                                      (                                          Z                      C                                        )                                                                                                          (        18        )            where the equality in equation (18) is true up to some constant factor. To evaluate p(y|Z), we distinguish between the Gaussian and non-Gaussian cases. For brevity, focus is given to the Gaussian case and then these results are extrapolated to the non-Gaussian case. We know that
                                          p            ⁡                          (                              y                |                Z                            )                                =                                    exp              ⁡                              (                                                      -                                          1                                              σ                        n                        2                                                                              ⁢                                                                                  y                                                                                    ∑                      Z                                              -                        1                                                              2                                                  )                                                    det              ⁡                              (                                  ∑                  Z                                )                                                    ,                                  ⁢                              with            ⁢                                                  ⁢                          ∑              Z                                =                                    I              M                        +                                                            σ                  x                  2                                                  σ                  n                  2                                            ⁢                              Ψ                Z                            ⁢                                                Ψ                  Z                  H                                .                                                                  ⁢                Here                                                    ,                              Ψ            Z                    =                      [                                                                                                                              Ψ                                                  Z                          1                                                                                                                                                                                          Ψ                                                          Z                              ′                                                                                ]                                                ,                                                  where                          ⁢                                                      :                                                                                                                                              ⁢                                                                  ⁢                                  Ψ                                      Z                    ′                                                              =                              [                                                                                                    Ψ                                                  Z                          2                                                                                                                                    Ψ                                                  Z                          3                                                                                                            …                                                                                                                                            Ψ                                                          Z                              C                                                                                ]                                                .                                                                                                                                                    (        19        )            
Using the matrix inversion lemma, Σz−1 may be written as:
                                                                        ∑                Z                                  -                  1                                            ⁢                              =                                ⁢                                                      (                                                                  I                        M                                            +                                                                                                    σ                            x                            2                                                                                σ                            n                            2                                                                          ⁢                                                  Ψ                          Z                                                ⁢                                                  Ψ                          Z                          H                                                                                      )                                                        -                    1                                                                                                                          =                            ⁢                                                (                                                            I                      M                                        +                                                                                            σ                          x                          2                                                                          σ                          n                          2                                                                    ⁢                                              Ψ                                                  Z                          1                                                                    ⁢                                              Ψ                                                  Z                          1                                                H                                                              +                                                                                            σ                          x                          2                                                                          σ                          n                          2                                                                    ⁢                                              Ψ                                                  Z                          ′                                                                    ⁢                                              Ψ                                                  Z                          ′                                                H                                                                              )                                                  -                  1                                                                                                        =                            ⁢                                                ∑                                      Z                    1                                                        -                    1                                                  ⁢                                                      -                                                                  σ                        x                        2                                                                    σ                        n                        2                                                                              ⁢                                                            ∑                                              Z                        1                                                                    -                        1                                                              ⁢                                                                                            Ψ                                                      Z                            ′                                                                          ⁡                                                  (                                                                                    I                                                              Z                                ′                                                                                      +                                                                                                                            σ                                  x                                  2                                                                                                  σ                                  n                                  2                                                                                            ⁢                                                              Ψ                                                                  Z                                  ′                                                                H                                                            ⁢                                                                                                ∑                                                                      Z                                    1                                                                                                        -                                    1                                                                                                  ⁢                                                                  Ψ                                                                      Z                                    ′                                                                                                                                                                                )                                                                                            -                        1                                                                                                                                                                                  ⁢                                                Ψ                                      Z                    ′                                    H                                ⁢                                  ∑                                      Z                    1                                                        -                    1                                                                                                          (        20        )            where
      ∑          Z      1        ⁢      =                  I        M            +                                    σ            x            2                                σ            n            2                          ⁢                  Ψ                      Z            1                          ⁢                              Ψ                          Z              1                        H                    .                    As ΨZ1 and ΨZ′ are almost orthogonal (i.e., ΨZ1HΨZ′=ΨZ′HΨZ1≃0), equation (20) becomes:
                                                                        ∑                Z                                  -                  1                                            ⁢                              =                                ⁢                                                      I                    M                                    -                                                                                    σ                        x                        2                                                                    σ                        n                        2                                                              ⁢                                                                                            Ψ                                                      Z                            1                                                                          ⁡                                                  (                                                                                    I                                                              Z                                1                                                                                      +                                                                                                                            σ                                  x                                  2                                                                                                  σ                                  n                                  2                                                                                            ⁢                                                              Ψ                                                                  Z                                  1                                                                H                                                            ⁢                                                              Ψ                                                                  Z                                  1                                                                                                                                              )                                                                                            -                        1                                                              ⁢                                          Ψ                                              Z                        1                                            H                                                        -                                                                                                                      ⁢                                                                    σ                    x                    2                                                        σ                    n                    2                                                  ⁢                                                                            Ψ                                              Z                        ′                                                              ⁡                                          (                                                                        I                                                      Z                            ′                                                                          +                                                                                                            σ                              x                              2                                                                                      σ                              n                              2                                                                                ⁢                                                      Ψ                                                          Z                              ′                                                        H                                                    ⁢                                                      Ψ                                                          Z                              ′                                                                                                                          )                                                                            -                    1                                                  ⁢                                  Ψ                                      Z                    ′                                    H                                                                                                        =                            ⁢                                                -                                      I                    M                                                  +                                  (                                                            I                      M                                        -                                                                                            σ                          x                          2                                                                          σ                          n                          2                                                                    ⁢                                                                                                    Ψ                                                          Z                              1                                                                                ⁡                                                      (                                                                                          I                                                                  Z                                  1                                                                                            +                                                                                                                                    σ                                    x                                    2                                                                                                        σ                                    n                                    2                                                                                                  ⁢                                                                  Ψ                                                                      Z                                    1                                                                    H                                                                ⁢                                                                  Ψ                                                                      Z                                    1                                                                                                                                                        )                                                                                                    -                          1                                                                    ⁢                                              Ψ                                                  Z                          1                                                H                                                                              )                                +                                                                                                      ⁢                              (                                                      I                    M                                    -                                                                                    σ                        x                        2                                                                    σ                        n                        2                                                              ⁢                                                                                            Ψ                                                      Z                            ′                                                                          ⁡                                                  (                                                                                    I                                                              Z                                ′                                                                                      +                                                                                                                            σ                                  x                                  2                                                                                                  σ                                  n                                  2                                                                                            ⁢                                                              Ψ                                                                  Z                                  ′                                                                H                                                            ⁢                                                              Ψ                                                                  Z                                  ′                                                                                                                                              )                                                                                            -                        1                                                              ⁢                                          Ψ                                              Z                        ′                                            H                                                                      )                                                                                        ≃                            ⁢                                                -                                      I                    M                                                  +                                                      (                                                                  I                        M                                            +                                                                                                    σ                            x                            2                                                                                σ                            n                            2                                                                          ⁢                                                  Ψ                                                      Z                            1                                                                          ⁢                                                  Ψ                                                      Z                            1                                                    H                                                                                      )                                                        -                    1                                                  +                                                                            (                                                                        I                          M                                                +                                                                                                            σ                              x                              2                                                                                      σ                              n                              2                                                                                ⁢                                                      Ψ                                                          Z                              ′                                                                                ⁢                                                      Ψ                                                          Z                              ′                                                        H                                                                                              )                                                              -                      1                                                        .                                                                                        (        21        )            
Continuing in the same manner, it is easy to show that:
                              ∑          Z                      -            1                          ⁢                  ≃                                                    -                                  (                                      C                    -                    1                                    )                                            ⁢                              I                M                                      +                                          ∑                                  i                  =                  1                                C                            ⁢                                                                    (                                                                  I                        M                                            +                                                                                                    σ                            x                            2                                                                                σ                            n                            2                                                                          ⁢                                                  Ψ                                                      Z                            i                                                                          ⁢                                                  Ψ                                                      Z                            i                                                    H                                                                                      )                                                        -                    1                                                  .                                                                        (        22        )            Thus, we can write:
                              exp          ⁡                      (                                          -                                  1                                      σ                    n                    2                                                              ⁢                                                                  y                                                                    ∑                  Z                                      -                    1                                                  2                                      )                          ≃                              exp            ⁡                          (                                                                    C                    -                    1                                                        σ                    n                    2                                                  ⁢                                                                          y                                                        2                                            )                                ⁢                                    ∏                              i                =                1                            C                        ⁢                                                  ⁢                          exp              ⁡                              (                                                      -                                          1                                              σ                        n                        2                                                                              ⁢                                                                                  y                                                                                    ∑                                              z                        i                                                                    -                        1                                                              2                                                  )                                                                        (        23        )            where
      ∑    Z          -      1        ⁢      =                  I        M            +                                    σ            x            2                                σ            n            2                          ⁢                  Ψ                      Z            i                          ⁢                              Ψ                          Z              i                        H                    .                    Using a similar procedure, we can decompose det (ΣZ) as:
                              det          ⁡                      (                          ∑              Z                        )                          =                ⁢                  det          ⁡                      (                                          I                M                            +                                                                    σ                    x                    2                                                        σ                    n                    2                                                  ⁢                                  Ψ                                      Z                    1                                                  ⁢                                  Ψ                                      Z                    1                                    H                                            +                                                                    σ                    x                    2                                                        σ                    n                    2                                                  ⁢                                  Ψ                                      Z                    ′                                                  ⁢                                  Ψ                                      Z                    ′                                    H                                                      )                                                  =                ⁢                              det            ⁡                          (                                                I                  M                                +                                                                            σ                      x                      2                                                              σ                      n                      2                                                        ⁢                                      Ψ                                          Z                      1                                                        ⁢                                      Ψ                                          Z                      1                                        H                                                              )                                ⁢                      det            ⁡                          (                                                I                  M                                +                                                                            σ                      x                      2                                                              σ                      n                      2                                                        ⁢                                      Ψ                                          Z                      ′                                        H                                    ⁢                                                            ∑                                              Z                        1                                                                    -                        1                                                              ⁢                                          Ψ                                              Z                        ′                                                                                                        )                                ⁢                                          ⁢                      (            24            )                                                  ≃                ⁢                              det            ⁡                          (                                                I                  M                                +                                                                            σ                      x                      2                                                              σ                      n                      2                                                        ⁢                                      Ψ                                          Z                      1                                                        ⁢                                      Ψ                                          Z                      1                                        H                                                              )                                ⁢                      det            ⁡                          (                                                I                  M                                +                                                                            σ                      x                      2                                                              σ                      n                      2                                                        ⁢                                      Ψ                    Z                                    ⁢                                      Ψ                                          Z                      ′                                        H                                                              )                                ⁢                                          ⁢                      (            25            )                                                            =                    ⁢                                    det              ⁡                              (                                  ∑                                      Z                    1                                                  )                                      ⁢                          det              ⁡                              (                                  ∑                                      Z                    ′                                                  )                                                    ,                                  ⁢                  (          26          )                    where in going from equation (24) to equation (25), we used the fact that ΨZ1 and ΨZ′ are almost orthogonal. Continuing in the same manner, it can be seen that:
                              det          ⁡                      (                          ∑              Z                        )                          ≃                              ∏                          i              =              1                        C                    ⁢                                          ⁢                                    det              ⁡                              (                                  ∑                                      Z                    i                                                  )                                      .                                              (        27        )            
Combining equations (23) and (27), we obtain (up to an irrelevant multiplicative factor):
                              p          ⁡                      (                          y              |              Z                        )                          ≃                              ∏                          i              =              1                        C                    ⁢                                    p              ⁡                              (                                  y                  |                                      Z                    i                                                  )                                      .                                              (        28        )            
Orthogonality allows us to reach the same conclusion of equation (28) for the non-Gaussian case. Combining equations (18) and (28), we may write:p(Z|y)≃πi=1Cp(Zi|y),  (29)which applies equally to the Gaussian and non-Gaussian cases.
In evaluating the expectation, we again distinguish between the Gaussian and non-Gaussian cases. The following focusses on the non-Gaussian case for which [xZ|y]=(ΨZHΨZ)−1ΨZHy. Using the decomposition into semi-orthogonal clusters ΨZ=[ΨZ1 ΨZ2 . . . ΨZC], we may write:
                                                        (                                                Ψ                  Z                  H                                ⁢                                  Ψ                  Z                                            )                                      -              1                                ⁢                      Ψ            Z            H                    ⁢          y                =                                            [                                                                                                                  Ψ                                                  Z                          1                                                H                                            ⁢                                              Ψ                                                  Z                          1                                                                                                                                                                        Ψ                                                  Z                          1                                                H                                            ⁢                                              Ψ                                                  Z                          2                                                                                                                          …                                                                                                      Ψ                                                  Z                          1                                                H                                            ⁢                                              Ψ                                                  Z                          C                                                                                                                                                          ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                                                                      Ψ                                                  Z                          C                                                H                                            ⁢                                              Ψ                                                  Z                          1                                                                                                                                                                        Ψ                                                  Z                          C                                                H                                            ⁢                                              Ψ                                                  Z                          2                                                                                                                          …                                                                                                      Ψ                                                  Z                          C                                                H                                            ⁢                                              Ψ                                                  Z                          C                                                                                                                                ]                                      -              1                                ⁢                                                                                                       [                                                                                                                                                      Ψ                                                              Z                                1                                                            H                                                        ⁢                            y                                                                                                                                                ⋮                                                                                                                                                                                Ψ                                                              Z                                C                                                            H                                                        ⁢                            y                                                                                                                ]                                    ≃                                      [                                                                                  ⁢                                                                                                                                                                                      (                                                                                                      Ψ                                                                          Z                                      1                                                                        H                                                                    ⁢                                                                      Ψ                                                                          Z                                      1                                                                                                                                      )                                                                                            -                                1                                                                                      ⁢                                                          Ψ                                                              Z                                1                                                            H                                                        ⁢                            y                                                                                                                                                ⋮                                                                                                                                                                                                                (                                                                                                      Ψ                                                                          Z                                      C                                                                        H                                                                    ⁢                                                                      Ψ                                                                          Z                                      C                                                                                                                                      )                                                                                            -                                1                                                                                      ⁢                                                          Ψ                                                              Z                                C                                                            H                                                        ⁢                            y                                                                                                                ]                                                  ;                                  i                  .                  e                  .                                            ,                                                                  ⁡                                      [                                                                  x                        Z                                            |                      y                                        ]                                                  ≃                                                      [                                                                                                                                                    ⁡                                                          [                                                                                                x                                                                      Z                                    1                                                                                                  |                                y                                                            ]                                                                                                                                                                            ⋮                                                                                                                                                                              ⁡                                                          [                                                                                                x                                                                      Z                                    C                                                                                                  |                                y                                                            ]                                                                                                                                            ]                                    .                                                                                        (        30        )            
Orthogonality allows us to write an identical expression to equation (30) in the Gaussian case.
In order to see how (semi)orthogonality helps with the MMSE evaluation, we substitute the decomposed expressions of equations (29) and (30) into equation (17) to yield:
                              x          MMSE                =                                            ∑                              Z                ⋐                                  ⋃                                      S                    i                                                                        ⁢                                          p                ⁡                                  (                                      Z                    |                    y                                    )                                            ⁢                                              ⁡                                  [                                                            x                      |                      y                                        ,                    Z                                    ]                                                              ≃                                    ∑                                                                    Z                    i                                    ⋐                                      S                    i                                                  ,                                  i                  =                  1                                ,                …                ,                C                                      ⁢                                          ∏                i                            ⁢                                                          ⁢                                                p                  ⁡                                      (                                                                  Z                        i                                            |                      y                                        )                                                  ⁢                                                                                               [                                                                                                                                                                ⁡                                                              [                                                                                                      x                                    |                                    y                                                                    ,                                                                      Z                                    1                                                                                                  ]                                                                                                                                                                                                                                                      ⁡                                                              [                                                                                                      x                                    |                                    y                                                                    ,                                                                      Z                                    2                                                                                                  ]                                                                                                                                                                                          ⋮                                                                                                                                                                                            ⁡                                                              [                                                                                                      x                                    |                                    y                                                                    ,                                                                      Z                                    C                                                                                                  ]                                                                                                                                                        ]                                        =                                          [                                                                                                                                                                  ∑                                                                                                      Z                                    1                                                                    ⋐                                                                      S                                    1                                                                                                                              ⁢                                                                                                p                                  ⁡                                                                      (                                                                                                                  Z                                        1                                                                            |                                      y                                                                        )                                                                                                  ⁢                                                                                                    ⁡                                                                      [                                                                                                                  x                                        |                                        y                                                                            ,                                                                              Z                                        1                                                                                                              ]                                                                                                                                                                                                                                                                                                                          ∑                                                                                                      Z                                    2                                                                    ⋐                                                                      S                                    2                                                                                                                              ⁢                                                                                                p                                  ⁡                                                                      (                                                                                                                  Z                                        2                                                                            |                                      y                                                                        )                                                                                                  ⁢                                                                                                    ⁡                                                                      [                                                                                                                  x                                        |                                        y                                                                            ,                                                                              Z                                        2                                                                                                              ]                                                                                                                                                                                                                                                            ⋮                                                                                                                                                                                              ∑                                                                                                      Z                                    C                                                                    ⋐                                                                      S                                    C                                                                                                                              ⁢                                                                                                p                                  ⁡                                                                      (                                                                                                                  Z                                        C                                                                            |                                      y                                                                        )                                                                                                  ⁢                                                                                                    ⁡                                                                      [                                                                                                                  x                                        |                                        y                                                                            ,                                                                              Z                                        C                                                                                                              ]                                                                                                                                                                                                                          ]                                                                                                                              (        31        )            where the last line follows from the fact that ΣZip(Zi|y)=1. Thus, the semi-orthogonality of the columns in the sensing matrix allows us to obtain the MMSE estimate of x in a divide-and-conquer manner by estimating the non-overlapping sections of x independently from each other. Other structural properties of Ψ can be utilized to reduce further the complexity of the MMSE estimation. For example, the orthogonal clusters exhibit some form of similarity and the columns within a particular cluster are also related to each other.
Thus, a method of performing structure-based Bayesian sparse signal reconstruction solving the aforementioned problems is desired.